DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.CP.2023.43

Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper)

Authors: Kyle E. C. Booth

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.

Cite as

Kyle E. C. Booth. Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 43:1-43:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{booth:LIPIcs.CP.2023.43,
  author =	{Booth, Kyle E. C.},
  title =	{{Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{43:1--43:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.43},
  URN =		{urn:nbn:de:0030-drops-190805},
  doi =		{10.4230/LIPIcs.CP.2023.43},
  annote =	{Keywords: Qubit routing, quantum computing, constraint programming, combinatorial optimization}
}

Search Results

Documents authored by Booth, Kyle E. C.

Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message